﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.Rob
{
    class MainProkect
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 1,3,1,3,100};
            Console.WriteLine(Rob(nums));
            Console.ReadKey();
        }

        /// <summary>
        /// 我自己做出来的动态规划（i和i-1）和贪心算法很像
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int Rob(int[] nums)
        {
            if (nums.Length == 0)
            {
                return 0;
            }
            else if (nums.Length == 1)
            {
                return nums[0];
            }
            int[,] dp = new int[nums.Length,2];//0:表示i-1个没有偷窃  1：表示i-1个有偷窃
            dp[0,0] = 0;
            dp[0,1] = nums[0];
            dp[1, 0] = dp[0, 1];
            dp[1, 1] = nums[1];
            int maxValue = Math.Max(Math.Max(dp[0, 0], dp[0, 1]), Math.Max(dp[1, 0], dp[1, 1]));
            for (int i = 2; i < nums.Length; i++)
            {
                dp[i, 0] = Math.Max(dp[i - 1, 1], dp[i - 1, 0]);
                dp[i, 1] = Math.Max(dp[i - 2, 1] , dp[i - 2, 0]) + nums[i];
                maxValue = Math.Max(maxValue, Math.Max(dp[i, 0], dp[i, 1]));
            }
            return maxValue;
        }
    }
}
